﻿#ifndef BinarySearchTree_h__
#define BinarySearchTree_h__

/********************************************************************
	创建于:		2011/04/22
	创建于:		22:4:2011   15:06
	基本文件:	BinarySearchTree
	文件扩展:	h
	作者:		王凯
	
	目的:		二叉查找树
*********************************************************************/

#include <stdio.h>

#ifndef NULL
#define NULL ((void*) 0)
#endif

template<typename Object>
class BinarySearchTree
{
public:
	//二叉树节点
	struct BinaryNode
	{
		//左子节点
		BinaryNode* left;
		//右子节点
		BinaryNode* right;
		//节点数据
		Object data;
		BinaryNode(BinaryNode* l, BinaryNode* r,const Object& x)
			:left(l), right(r), data(x){}
	};
	//无参数的构造函数
	BinarySearchTree():m_Root(NULL), m_iSize(0){}
	//拷贝构造函数
	BinarySearchTree(const BinarySearchTree& bst):m_Root(NULL)，m_iSize(0)
	{
		*this = bst;
	}
	//析构函数
	~BinarySearchTree(){ makeEmpty(m_Root);}
	//赋值运算符重载
	const BinarySearchTree& operator=(const BinarySearchTree& bst)
	{
		if(this != bst)
		{
			makeEmpty(m_Root);
			m_Root = clone(bst.m_Root);
		}
		return *this;
	}

	//判断参数是否存在于该二叉树中，存在返回真，否则返回假
	bool contains(const Object& x)const{ return contains(x, m_Root);}
	//插入一个元素到二叉树中，如果成功则返回真，否则返回假
	bool insert(const Object& x){ return insert(x, m_Root);}
	//从二叉树中删除一个元素，如果成功则返回真，否则返回假
	bool remove(const Object& x){ return remove(x, m_Root);}
	//寻找树中最小的元素并返回
	Object findMin()const{ return findMin(m_Root)->data;}
	//寻找树中最大的元素并返回
	Object findMax()const{ return findMax(m_Root)->data;}
	//返回二叉树现有元素个数
	int size()const{return m_iSize;}
private:

	//************************************
	// 方法:			insert
	// 全名:  		BinarySearchTree<Object>::insert
	// 访问权限:		private 
	// 返回类型:   	bool
	// 限定符: 		
	// 参数: 		const Object & x
	// 参数: 		BinaryNode *  & root
	//************************************
	bool insert(const Object& x, BinaryNode* &root)
	{
		//首先判断节点是否为空，空则需要在该位置插入一个值
		if(root == NULL)
		{
			root = new BinaryNode(NULL, NULL, x);
			m_iSize++;
			return true;
		}
		//将插入点向根节点的左子节点或右子节点移动
		else if(root->data > x)
			insert(x, root->left);
		else if(root->data < x)
			insert(x, root->right);
		//失败（元素存在重复）
		else
			return false;
	}

	//************************************
	// 方法:			remove
	// 全名:  		BinarySearchTree<Object>::remove
	// 访问权限:		private 
	// 返回类型:   	bool
	// 限定符: 		
	// 参数: 		const Object & x
	// 参数: 		BinaryNode *  & root
	//************************************
	bool remove(const Object& x, BinaryNode* &root)
	{
		//首先判断节点是否为空，空则表示没有找到该元素
		if(root == NULL)
			return false;
		//向根节点的左、右子树搜索
		if(root->data > x)
			remove(x, root->left);
		else if(root->data < x)
			remove(x, root->right);
		//找到该节点并且该节点存在左右子树
		else if(root->right != NULL && root->left != NULL)
		{
			//将该节点的右子树中最小元素替换到该节点的位置
			root = findMin(root->right);
			//然后从该节点的右子树中删除最小元素
			remove(root->data, root->right);
			m_iSize--;
			return true;
		}
		//找到该节点并且该节点至多有一个子树
		else
		{
			//暂存该节点
			BinaryNode* t = root;
			//然后用该节点的任意有效节点替换之
			root = (root->left!= NULL)?root->left:root->right;
			//释放暂存的节点
			delete t;
			m_iSize--;
			return true;
		}
	}

	//************************************
	// 方法:			findMin
	// 全名:  		BinarySearchTree<Object>::findMin
	// 访问权限:		private 
	// 返回类型:   	BinaryNode*
	// 限定符: 		const
	// 参数: 		BinaryNode * p
	//************************************
	BinaryNode* findMin(BinaryNode* p)const
	{
		//不断的递归到根节点的最左节点
		if(p->left != NULL)
			findMin(p->left	);
		else
			return p;
	}

	//************************************
	// 方法:			findMax
	// 全名:  		BinarySearchTree<Object>::findMax
	// 访问权限:		private 
	// 返回类型:   	BinaryNode*
	// 限定符: 		const
	// 参数: 		BinaryNode * p
	//************************************
	BinaryNode* findMax(BinaryNode* p)const
	{
		//不断的递归到根节点的最右节点
		if(p->right != NULL)
			findMax(p->right);
		else
			return p;
	}

	//************************************
	// 方法:			contains
	// 全名:  		BinarySearchTree<Object>::contains
	// 访问权限:		private 
	// 返回类型:   	bool
	// 限定符: 		const
	// 参数: 		const Object & x
	// 参数: 		const BinaryNode * p
	//************************************
	bool contains(const Object&x, const BinaryNode* p)const
	{
		//递归搜索到节点的左、右节点
		if(p == NULL)
			return false;
		else if(p->data > x)
			return contains(x, p->left);
		else if(p->data < x)
			return contains(x, p->right);
	}

	//************************************
	// 方法:			makeEmpty
	// 全名:  		BinarySearchTree<Object>::makeEmpty
	// 访问权限:		private 
	// 返回类型:   	void
	// 限定符: 		
	// 参数: 		BinaryNode *  & p
	//************************************
	void makeEmpty(BinaryNode* &p)
	{
		//释放p及其子节点
		if(p != NULL)
		{
			makeEmpty(p->left);
			makeEmpty(p->right);
			delete p;
		}
		p = NULL;
	}

	//************************************
	// 方法:			clone
	// 全名:  		BinarySearchTree<Object>::clone
	// 访问权限:		private 
	// 返回类型:   	BinaryNode*
	// 限定符: 		
	// 参数: 		BinaryNode * p
	//************************************
	BinaryNode* clone(BinaryNode* p)
	{
		if(p == NULL)
			return NULL;

		return BinaryNode(clone(p->left), clone(p->right), p->data);
	}
private:
	//根节点指针
	BinaryNode* m_Root;
	//树大小
	int m_iSize;
};
#endif // BinarySearchTree_h__
